package amc;


import java.util.*;
import java.util.stream.Collectors;

/**
 * @className: number3
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/3/24 10:32
 */
public class number3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxCacheSize = Integer.parseInt(scanner.nextLine());
        int operationSize =Integer.parseInt(scanner.nextLine());
        CacheSystem cache = new CacheSystem(maxCacheSize);
        int i = 0;
        while(i < operationSize && scanner.hasNextLine() ){
            String operation = scanner.nextLine();
            String[] split = operation.split("\\s+");
            // get 操作
            if(split.length == 2){
                cache.get(split[1]);
            }else if(split.length == 3){
                cache.put(split[1], Integer.parseInt(split[2]));
            }
            i++;
        }
        String collect = cache.filePriorityQueue.stream().map(x -> x.fileName).collect(Collectors.joining(","));
        if(Objects.isNull(collect) || collect.length() == 0){
            System.out.println("None");
        }
        System.out.println(collect);
    }
    public static class CacheSystem{
       public int cacheSize;
       public int usedSize ;
       public Map<String , FileDescriptor> fileDescriptors = new HashMap();
       public PriorityQueue<FileDescriptor> filePriorityQueue = new PriorityQueue<>();
       public CacheSystem(int cacheSize){
            this.cacheSize = cacheSize;
       }
       public boolean isFull(){
           return cacheSize - usedSize <= 0;
       }
       public boolean isEmputy(){
           return usedSize <= 0 ;
       }
       public boolean require(int require ){
           return cacheSize - usedSize - require >= 0;
       }
       public void get(String fileName){
           FileDescriptor fileDescriptor = fileDescriptors.get(fileName);
           filePriorityQueue.remove(fileDescriptor);
           if(Objects.nonNull(fileDescriptor)){
               fileDescriptor.accessTime = System.currentTimeMillis();
               fileDescriptor.accessTime = fileDescriptor.accessTime + 1;
               filePriorityQueue.add(fileDescriptor);
           }
       }
       public void put(String fileName , int require){
            if(require(require)){
                usedSize += require;
                FileDescriptor fileDescriptor = new FileDescriptor(fileName, require);
                filePriorityQueue.add(fileDescriptor);
                fileDescriptors.put(fileName , fileDescriptor);
            }else{
               while(!require(require) && !isEmputy()){
                   FileDescriptor peek = filePriorityQueue.remove();
                   fileDescriptors.remove(peek.fileName);
                   usedSize -= peek.fileSize ;
               }
               if(require(require)){
                   FileDescriptor fileDescriptor = new FileDescriptor(fileName, require);
                   filePriorityQueue.add(fileDescriptor);
                   fileDescriptors.put(fileName , fileDescriptor);
               }
            }
       }
    }
    public static class FileDescriptor implements Comparable<FileDescriptor> {
        public String fileName ;
        public int fileSize ;
        public int accessCnt ;
        public long accessTime ;
        public FileDescriptor(String fileName , int require){
            this.fileName = fileName;
            this.fileSize = require ;
        }
        @Override
        public int compareTo(FileDescriptor o) {
            int rs = this.accessCnt - o.accessCnt;
            if(0 == rs){
                return (int)(this.accessTime - o.accessTime);
            }
            return rs;
        }
    }
}
